// https://www.lintcode.com/problem/permutations-ii/

class Solution {
public:
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    // void helper(vector<int> nums, vector<vector<int>>& result, int start, int end) {
    //     if (start == end)
    //     {
    //         if (find(result.begin(), result.end(), nums) == result.end())
    //             result.push_back(nums);
    //         return;
    //     }
    //     for (int i = start; i <= end; ++i)
    //     {
    //         swap(nums[start], nums[i]);
    //         helper(nums, result, start + 1, end);
    //         swap(nums[start], nums[i]);
    //     }
    // }
    // vector<vector<int>> permuteUnique(vector<int> &nums) {
    //     vector<vector<int>> result;
    //     if (nums.empty()) 
    //     {   
    //         result.push_back(vector<int>()); //别忘了
    //         return result;
    //     }
    //     helper(nums, result, 0, nums.size() - 1);
    //     return result;
    // }
    
    //法二：先sort
    void helper(vector<int> nums, vector<vector<int>>& result, int start, int end) {
        if (start == end)
        {
            result.push_back(nums);
            return;
        }
        for (int i = start; i <= end; ++i)
        {
            // if (i != start && nums[i] == nums[start]) continue
            // 不能仅仅这样判断，可能后面的两个数字一样，但都和start不一样
            // if (i > 0 && nums[i] == nums[i - 1]) continue; 
            // 不是和0比，否则后面helper时直接就退出了
            // Input
            // [1,1,2]
            // Output
            // [[1,2,1],[2,1,1]]
            // Expected
            // [[1,1,2],[1,2,1],[2,1,1]]
            if (i > start && (nums[i] == nums[start] || nums[i] == nums[i - 1])) continue;  // 不换的情况：和start值一样；一样的值已经换过了
            swap(nums[start], nums[i]);
            helper(nums, result, start + 1, end);
            swap(nums[start], nums[i]);
        }
    }
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        if (nums.empty()) 
        {   
            result.push_back(vector<int>());
            return result;
        }
        helper(nums, result, 0, nums.size() - 1);
        return result;
    }
};
// WA：[-1,2,0,-1,1,0,1]

class Solution {
public:
    void dfs(vector<vector<int>>& res, vector<int>& nums, int start, int end) {
        if (start == end) {
            res.push_back(nums);
        }
        set<int> swp;
        for (int i = start; i <= end; ++i) {
            if (swp.find(nums[i]) != swp.end()) continue;
            swp.insert(nums[i]);
            swap(nums[start], nums[i]);
            dfs(res, nums, start + 1, end);
            swap(nums[start], nums[i]);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        dfs(res, nums, 0, nums.size() - 1);
        return res;
    }
};


class Solution {
public:
    void dfs(vector<vector<int>>& res, vector<int>& nums, vector<bool>& visited, vector<int>& tmp) {
        if (tmp.size() == nums.size()) res.push_back(tmp);
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) continue; 
        //限制一下重复数字的访问顺序即可，保证每次填入的数一定是这个数所在重复数集合中从左往右第一个未被填过的数字
            tmp.push_back(nums[i]);
            visited[i] = true;
            dfs(res, nums, visited, tmp);
            tmp.pop_back();
            visited[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<bool> visited(nums.size(), false);
        vector<int> tmp;
        sort(nums.begin(), nums.end()); // 注意要先排序
        dfs(res, nums, visited, tmp);
        return res;
    }
};

// 举个栗子，对于两个相同的数11，我们将其命名为1a1b, 1a表示第一个1，1b表示第二个1； 
// 那么，不做去重的话，会有两种重复排列 1a1b, 1b1a， 我们只需要取其中任意一种排列； 
// 为了达到这个目的，限制一下1a, 1b访问顺序即可。 比如我们只取1a1b那个排列的话，
// 只有当visit nums[i-1]之后我们才去visit nums[i]， 也就是如果!visited[i-1]的话则continue